﻿//力扣：77. 组合
//链接：https://leetcode.cn/problems/combinations/description/


//方法：DFS

//算法原理：
//题⽬要求我们从 1 到 n 中选择 k 个数的所有组合，其中不考虑顺序。也就是说，[1, 2] 和[2, 1] 等价。
//我们需要找出所有的组合，但不能重复计算相同元素的不同顺序的组合。对于选择组合，我们需要进⾏如下流程：
//1. 所有元素分别作为⾸位元素进⾏处理；
//2. 在之后的位置上同理，选择所有元素分别作为当前位置元素进⾏处理；
//3. 为避免计算重复组合，规定选择之后位置的元素时必须⽐前⼀个元素⼤，这样就不会有重复的组合（[1, 2] 和[2, 1] 中[2, 1] 不会出现）。
//
//具体实现⽅法如下：
//1. 定义⼀个⼆维数组和⼀维数组。⼆维数组⽤来记录所有组合，⼀维数组⽤来记录当前状态下的组合。
//2. 遍历 1 到 n - k + 1，以当前数作为组合的⾸位元素进⾏递归（从 n - k + 1 到 n 作为⾸位元素时，组合中⼀定不会存在 k 个元素）。
//3. 递归函数的参数为两个数组、当前步骤以及 n 和 k。递归流程如下：
//    a.结束条件：当前组合中已经有 k 个元素，将当前组合存进⼆维数组并返回。
//        ▪ 剪枝：如果当前位置之后的所有元素放⼊组合也不能满⾜组合中存在 k 个元素，直接返回。
//    b.从当前位置的下⼀个元素开始遍历到 n，将元素赋值到当前位置，递归下⼀个位置。
class Solution
{
public:
    vector<int> path;                  // 当前组合路径
    vector<vector<int>> ret;           // 存储所有组合结果
    int _n, len;                       // n 和 k 的值

    // 深度优先搜索，start 为当前递归的起始位置
    void dfs(int start)
    {
        
        if (path.size() == len)
        {
            ret.push_back(path);       // 如果当前路径长度等于 k，说明找到一个合法的组合，将当前路径加入结果集
            return;
        }

        // 从 start 开始，选择一个数并递归
        for (int i = start; i <= _n; i++)
        {
            path.push_back(i);         // 将当前元素添加到路径中

            dfs(i + 1);                // 递归处理下一个元素

            path.pop_back();           // 回溯，移除当前元素
        }
    }

    vector<vector<int>> combine(int n, int k)
    {
        _n = n;                        // 设置 n 的值
        len = k;                       // 设置 k 的值
        dfs(1);                        // 从 1 开始深度优先搜索
        return ret;                    // 返回所有组合结果
    }
};